/**************************************************
 * File: List.h                                    *
 *                                                *
 *                                                *
 **************************************************/

#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <list>

using std::list;

namespace ADT
{
	namespace Lists
	{
		//Dynamically Linked List
		template <typename Object>
		class List
		{
			public:
				//Constructors
				List (void);
				List (List & Copy);
				//Destructor
				~List (void);

				//Public Methods
				const Object & FindMin (void) const;
				const Object & FindMax (void) const;
				bool Contains (const Object & X) const;
				bool IsEmpty (void) const;
				int GetNumberOfNodes (void) const;

				void MakeEmpty (void);
				void InsertInOrder (const Object & X);
				void Insert (const Object & X);
				void Remove (const Object & X);

			private:
				//Private Members
				list<Object> ObjList;
				Object MinValue;
				Object MaxValue;
		};

		///////////////////////////
		// BST Class Definitions //
		///////////////////////////

		//Constructors
		template <typename Object>
		List<Object>::List (void)
		{
		}

		template <typename Object>
		List<Object>::List (List & Copy)
		{
			this->ObjList = Copy.ObjList;
		}

		//Destructor
		template <typename Object>
		List<Object>::~List (void)
		{
			this->MakeEmpty();
		}

		//Public Methods
		template <typename Object>
		const Object & List<Object>::FindMin (void) const
		{
			return this->MinValue;
		}

		template <typename Object>
		const Object & List<Object>::FindMax (void) const
		{
			return this->MaxValue;
		}

		template <typename Object>
		bool List<Object>::Contains (const Object & X) const
		{
			for (list<Object>::iterator i = this->ObjList.begin(); i < this->ObjList.end(); i++)
			{
				if (*i == X)
					return true;
			}
			return false;
		}

		template <typename Object>
		bool List<Object>::IsEmpty (void) const
		{
			if (this->ObjList.size() == 0)
				return true;
			else
				return false;
		}

		template <typename Object>
		int List<Object>::GetNumberOfNodes (void) const
		{
			return (int)this->ObjList.size();
		}

		template <typename Object>
		void List<Object>::MakeEmpty (void)
		{
			this->ObjList.clear();
		}

		template <typename Object>
		void List<Object>::InsertInOrder (const Object & X)
		{
			if (this->IsEmpty())
				this->ObjList.insert(this->ObjList.begin(), X);
			else
			{
				bool Inserted = false;
				for (list<Object>::iterator i = this->ObjList.begin(); i != this->ObjList.end(); i++)
				{
					if (*i > X)
					{
						this->ObjList.insert(i, X);
						Inserted = true;
						break;
					}
				}
				if (!Inserted)
					this->ObjList.push_back(X);
			}
		}

		template <typename Object>
		void List<Object>::Insert (const Object & X)
		{
			this->ObjList.push_back(X);
		}

		template <typename Object>
		void List<Object>::Remove (const Object & X)
		{
			this->ObjList.remove(X);
		}
	}
}

#endif